LeetCode 169、多数元素

一、题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

限制：

1 <= 数组长度 <= 50000

二、题目解析

题目明确说明了在这个数组中肯定有一个数字出现的次数超过数组长度的一半，可以假设这个数字是 x，并且假设每个数字的战斗力都是 1，那么其它所有数字、即非 x 的数字加起来的战斗力肯定是不如所有 x 加起来的战斗力。

那么我们可以制定以下的规则：

1、每个数字的战斗力都是 1，颜色相同的数字为同一组势力。

2、设置一个擂台，每个数字都需要轮番上擂台。

3、如果擂台上没有数字，那么该数字就是擂主。

4、如果擂台上已经有数字，但两方的势力不同，则同归于尽。

5、如果擂台上已经有数字，并且两方的势力一致，则擂主还是它，并且数量加 1。

具体操作如下：

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]

一开始，蓝色势力先登场，由于擂台上之前没有数字，那么蓝色数字 1 就是擂主了。

接下来，黄色势力 2 开始挑战，由于蓝色和黄色属于不同的势力、战斗力一致、都只有一个，因此两者同归于尽，擂台被清空。

擂台清空后，3 号登场成为了新的擂主。

2 号登场，擂台被清空。

2 号登场，擂台擂主为 2 号。

2 号登场，擂台擂主依旧为 2 号，并且个数为 2 个。

5 号登场，与 2 号不同势力，拉下一个擂主来，导致擂台上擂主依旧为 2 ，但个数下降为 1 个。

4 号登场，与 2 号不同势力，拉下一个擂主来，擂台被清空。

2 号登场，成为新的擂主，全部数字挑战完毕，2 号留在场上，它就是所求的那个数字。

为了帮助你更好的理解整个过程，我特意做了一组动画，点开可以查看：

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 剑指 Offer 39. 数组中出现次数超过一半的数字 ：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
class Solution {
    public int majorityElement(int[] nums) {

        // 统计擂台上擂主的个数
        int count = 0;

        // candidate 表示擂主的编号
        // 一开始，擂台上没有擂主
        int candidate = 0;

        // 数组中的所有数字开始轮番上擂台进行挑战，每个数字的战斗力均为 1
        // 1、相同势力的数字可以都停留在擂台上
        // 2、不同势力的数字会同归于尽
        for (int num : nums) {
            
            // 擂台上没有擂主时
            if (count == 0) {
                // 此时登场的 num 就是擂主
                candidate = num;
            }

            // 擂台上有擂主
            // 并且此时登场的 num 和擂主属于相同的势力
            // 那么两者都停留在场上
            if ( num == candidate){
                count += 1;

            // 否则说明此时登场的 num 和擂主属于不同的势力
            // num 会和一个擂主同归于尽
            }else{
                count -= 1;
            }
           
        }

        // 一轮遍历下来，停留在场上的擂主就是所求的数字
        return candidate;
    }
}